L'algorithme d'Euclide étendu - Vers le supérieur

Algorithme d'Euclide étendu

Soit  $a$ et  $b$ deux entiers naturels non nuls.

L'algorithme d'Euclide étendu consiste à déterminer simultanément :

• le PGCD de  $a$ et $b$  ;
• un couple $(u;v)\in {\mathbb{Z}}^2$ tel que $au+bv=\mathrm{PGCD}(a;b)$ .

Pour trouver le PGCD de  $a$ et $b$ , il s'agit d'effectuer classiquement l'algorithme d'Euclide.

On note $r_1$ , $r_2$ , ..., $r_{n-2}$ , $r_{n-1}$ les restes successifs obtenus, avec $r_{n-1}=\mathrm{PGCD}(a;b)$ , c'est-à-dire que l'algorithme termine en $n$ étapes ( $n-1$ étapes de $r_1$ à $r_{n-1}$ et une dernière étape pour se rendre compte que le reste suivant vaut $0$ ).

On note $q_1$ , $q_2$ , ..., $q_{n-2}$ , $q_{n-1}$ , $q_n$ les quotients successifs obtenus.
$\begin{array}{r}\begin{array}{|cccccc|}\hline \text{Étape}& \text{Dividende}& \text{Diviseur}& \text{Quotient}& \text{Reste}& \text{Division euclidienne avec reste isolé}\\ 1& a& b& q_1& r_1& r_1=a-b{q}_1\\ 2& b& r_1& q_2& r_2& r_2=b-r_1{q}_2\\ 3& r_1& r_2& q_3& r_3& r_3=r_1-r_2{q}_3\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ n-1& r_{n-3}& r_{n-2}& q_{n-1}& r_{n-1}& r_{n-1}=r_{n-3}-r_{n-2}{q}_{n-1}\\ n& r_{n-2}& r_{n-1}& q_n& r_n=0& r_n=0=r_{n-2}-r_{n-1}{q}_n\\ \hline\end{array}\end{array}$

En notant $r_{-1}=a$ et $r_0=b$ , on constate que les divisions euclidiennes en isolant les restes s'écrivent  $r_k=r_{k-2}-r_{k-1}{q}_k$  pour tout  $k\in \{1;...;n\}$ .

Pour trouver un couple $(u;v)\in {\mathbb{Z}}^2$ tel que $au+bv=\mathrm{PGCD}(a;b)$ , autrement dit tel que   $au+bv=r_{n-1}$ , l'idée-clef est que la relation de récurrence ci-dessus sur les restes $r_k$  « se transmet » aux coefficients $u$ et $v$ de l'égalité $au+bv=\mathrm{PGCD}(a;b)$ .

Plus précisément, on peut construire deux suites $(u_k{)}_{k\in \{-1;...;n\}}$ et $(v_k{)}_{k\in \{-1;...;n\}}$ en posant $\begin{array}{r}\{\begin{array}{l}{u}_{-1}=1\\ u_0=0\\ v_{-1}=0\\ v_0=1\\ r_k=a{u}_k+b{v}_k\text{ pour tout }k\in \{1;...;n\}.\end{array}\end{array}$   

La relation $r_k=a{u}_k+b{v}_k$ est également vraie pour $k=-1$ et $k=0$ . En effet,  $\begin{array}{r}{r}_{-1}=a=a\times 1+b\times 0=a{u}_{-1}+b{v}_{-1}\end{array}$  et  $\begin{array}{r}{r}_0=a=a\times 0+b\times 1=a{u}_0+b{v}_0\end{array}$ .

De plus, pour tout $k\in \{1;...;n\}$ tel que $u_{k-2}$ , $v_{k-2}$ , $u_{k-1}$ et $v_{k-1}$ ont déjà été construits,
on a :
$\begin{array}{rl}{r}_k& =r_{k-2}-r_{k-1}{q}_k\\ & =a{u}_{k-2}+b{v}_{k-2}-(a{u}_{k-1}+b{v}_{k-1})q_k\\ & =a(u_{k-2}-u_{k-1}{q}_k)+b(v_{k-2}-v_{k-1}{q}_k)\end{array}$  
si bien qu'il suffit de poser
$\begin{array}{r}{u}_k=u_{k-2}-u_{k-1}{q}_k\text{ et }{v}_k=v_{k-2}-v_{k-1}{q}_k\text{ pour tout }k\in \{1;...;n\}\end{array}$  et l'on construit ainsi les suites $(u_k{)}_{k\in \{-1;...;n\}}$ et $(v_k{)}_{k\in \{-1;...;n\}}$ .

En particulier, $a{u}_{n-1}+b{v}_{n-1}=r_{n-1}=\mathrm{PGCD}(a;b)$ , donc le couple $(u;v)=(u_{n-1};v_{n-1})$ vérifie l'égalité $au+bv=\mathrm{PGCD}(a;b)$ .

En pratique, pour calculer les termes des suites $(u_k)$ et $(v_k)$ :

• on applique l'algorithme d'Euclide pour $a$ et $b$ ;
• on initialise les suites $(u_k)$ et $(v_k)$ aux rangs $k=-1$ et $k=0$ ;
• on se sert des relations de récurrence permettant de calculer les termes $u_k$ et $v_k$ à partir des deux rangs précédents et du quotient $q_k$ (en présentant les calculs sous forme de tableau avec des lignes numérotées à partir de $L_{-1}$ , on constate que l'opération à faire est $L_k\leftarrow L_{k-2}-q_k{L}_{k-1}$ ).
  

Voici une suggestion de présentation de l'algorithme d'Euclide étendu :

Exemples

1. On souhaite déterminer un couple $(u;v)\in {\mathbb{Z}}^2$ tel que $156u+42v=\mathrm{PGCD}(156;42)$ .
On utilise l'algorithme d'Euclide étendu.

On en déduit que $\mathrm{PGCD}(156;42)=6$ et que $156\times 3+42\times (-11)=6$ .

2. On souhaite déterminer un couple $(u;v)\in {\mathbb{Z}}^2$ tel que $200u+116v=\mathrm{PGCD}(200;116)$ .
On utilise l'algorithme d'Euclide étendu.

On en déduit que $\mathrm{PGCD}(200;116)=4$  et que  $200\times (-11)+116\times 19=4$ .

Remarque

L'algorithme d'Euclide étendu ne donne pas seulement un couple $(u;v)\in {\mathbb{Z}}^2$ tel que  $au+bv=\mathrm{PGCD}(a;b)$  : il donne des couples $(u_k;v_k)\in {\mathbb{Z}}^2$ tels que $r_k=a{u}_k+b{v}_k$ à chaque étape de l'algorithme.